class Node:
    def __init__(self, elem=-1, lchild=None, rchild=None):
        self.elem = elem
        self.lchild = lchild
        self.rchild = rchild


class BinaryTree:
    def __init__(self):
        self.root = None  # 树根
        self.help_queue = []  # 辅助队列,记录父节点（新节点插入哪个节点下面）

    # 层次建树
    def level_build_tree(self, node: Node):
        self.help_queue.append(node)  # 入队
        if self.root is None:  # 树空
            self.root = node
        else:
            if self.help_queue[0].lchild is None:  # 左孩子为空，新节点为左孩子
                self.help_queue[0].lchild = node
            elif self.help_queue[0].rchild is None:  # 右孩子为空，新节点为右孩子，并出队父节点
                self.help_queue[0].rchild = node
                self.help_queue.pop(0)

    # 先序遍历
    def Pre_order(self, current_node: Node):
        if current_node:
            print(current_node.elem, end=' ')
            self.Pre_order(current_node.lchild)
            self.Pre_order(current_node.rchild)

    # 中序遍历
    def In_order(self, current_node: Node):
        if current_node:
            self.In_order(current_node.lchild)
            print(current_node.elem, end=' ')
            self.In_order(current_node.rchild)

    # 后序遍历
    def Past_order(self, current_node: Node):
        if current_node:
            self.Past_order(current_node.lchild)
            self.Past_order(current_node.rchild)
            print(current_node.elem, end=' ')

    # 层次遍历
    def level_order(self, current_node: Node):
        help_queue = []
        help_queue.append(self.root)  # 树根入队
        while help_queue:
            pop_node = help_queue.pop(0)
            print(pop_node.elem, end=' ')
            if pop_node.lchild:
                help_queue.append(pop_node.lchild)#左孩子入队
            if pop_node.rchild:
                help_queue.append(pop_node.rchild)#右孩子入队


if __name__ == '__main__':
    tree = BinaryTree()
    for i in range(1, 11):
        new_node = Node(i)  # 实例化结点
        tree.level_build_tree(new_node)  # 把节点放入树中
    print('前序遍历:', end='')
    tree.Pre_order(tree.root)

    print('\n先序遍历:', end='')
    tree.In_order(tree.root)

    print('\n先序遍历:', end='')
    tree.Past_order(tree.root)

    print('\n层次遍历:',end='')
    tree.level_order(tree.root)
